# 顺序字符串的基本操作
class StringList:
    # 默认的初始化字符串的函数
    def __init__(self):
        self.MaxStringSize = 256  # 允许放字符串的最大长度
        self.chars = ""
        self.length = 0

    # 创建一个字符串的函数
    def CreateString(self):
        stringSH = input("请输入字符串,请按回车结束输入：")
        if len(stringSH) > self.MaxStringSize:
            print("输入的字符序列超过分配的存储空间，超过的部分无法存入当前字符串中。")
            self.chars = stringSH[:self.MaxStringSize]  # 进行截取
        else:
            self.chars = stringSH

    # 字符串连接的函数
    def StringConcat(self, strSrc):
        lengthSrc = strSrc.length
        stringSrc = strSrc.chars
        if lengthSrc + len(self.chars) <= self.MaxStringSize:
            self.chars = self.chars + stringSrc
        else:
            print("两个字符串连接后的长度超过分配的内存，超过的部分无法显示。")
            size = self.MaxStringSize - len(self.chars)
            self.chars = self.chars + stringSrc[0:size]
        print("连接后的字符串为：", self.chars)

    # 从指定位置开始获取指定长度子字符串的函数
    def SubString(self, iPos, length):
        if iPos > len(self.chars) or iPos < 0 or length < 1 or (length > len(self.chars) - iPos):
            print("无法获取子串。")
        else:
            substr = self.chars[iPos:iPos + length]
            print("获取的字串为：", substr)

    def IndexBF(self, pos, T):
        global tag
        count = 0  # 用于统计匹配次数
        length = T.GetStringLength()
        if len(self.chars) < length:  # 判断当前串长度是否小于模式串长度
            print("模式串的长度大于主串的长度，无法进行字符串的模式匹配。")
        else:
            i = pos  # 变量i指示当前串待匹配的字符并令其初值为pos
            string = T.GetString()
            while i <= len(self.chars) - length:
                iT = i  # 用iT记下此时i值，此值被用于当前匹配失败后进行新一轮比较
                j = 0
                tag = False  # 默认匹配失败
                while j < length:
                    if self.chars[i] == string[j]:
                        i = i + 1
                        j = j + 1
                    else:
                        break
                if j == length:
                    print("匹配成功! 模式串在主串中首次出现的位置为", iT)
                    tag = True
                    break
                else:
                    i = iT + 1
                    count = count + 1
            if tag == False:
                print("匹配失败！")
            print("使用BF算法共进行了", count + 1, "次匹配")

    # 输出一个串的字符序列函数
    def StringTraverse(self):
        print(self.chars)

    # 获取串长度的函数
    def GetStringLength(self):
        return self.length

    # 获取串字符序列的函数
    def GetString(self):
        return self.chars

    # 获取模式串ListNext值的函数
    def GetListNext(self):
        ListNext = [None for x in range(0, 100)]
        ListNext[0] = -1
        k = -1
        j = 0
        while j < len(self.chars):
            if k == -1 or self.chars[j] == self.chars[k]:
                k = k + 1
                j = j + 1
                ListNext[j] = k
            else:
                k = ListNext[k]
        return ListNext

    # 获取模式串ListNextValue值的函数
    def GetListNextValue(self):
        ListNextValue = [None for x in range(0, 100)]
        ListNextValue[0] = -1
        k = -1
        j = 0
        while j < len(self.chars)-1:
            if k == -1 or self.chars[j] == self.chars[k]:
                k = k+1
                j = j+1
                if self.chars[j] != self.chars[k]:
                    ListNextValue[j] = k
                else:
                    ListNextValue[j] = ListNextValue[k]
            else:
                k = ListNextValue[k]
        return ListNextValue
    def IndexKMP(self, pos, T, ListNext_ListNextValue):
        i = pos
        j = 0
        count = 0       # 用于统计匹配次数
        length = T.GetStringLength()
        string = T.GetString()
        while i < len(self.chars) and j < length:
            if j == -1 or self.chars[i] == string[j]:
                i = i+1
                j = j+1
            else:
                j = ListNext_ListNextValue[j]
                count = count+1
        if j == length:
            print("匹配成功! 模式串在主串中首次出现的位置为", i-length)
        else:
            print("匹配失败！")
        print("共进行了", count+1, "次匹配")

if __name__ == '__main__':
    # stringSrc = StringList()    # 创建源字符串
    # stringSrc.CreateString()
    # print("源字符串为：" + stringSrc.chars)
    #
    # stringDst = StringList()  # 创建目标字符串
    # stringDst.CreateString()
    # print("字符串为：", end='')
    #
    # stringDst.StringConcat(stringSrc)  # 连接字符串
    #
    # position = int(input("请输入要从第几个位置截取："))  # 截取字符串
    # length = int(input("请输入要截取的长度："))
    # stringDst.SubString(position, length)

    # BF算法测试
    # S = StringList()
    # S.CreateString()
    # print("主串为：", end='')
    # S.StringTraverse()
    # T = StringList()
    # T.CreateString()
    # print("模式串为：", end='')
    # T.StringTraverse()
    # pos = int(input("请输入从主串的哪一位置开始串的模式匹配："))
    # print("匹配结果：", end='')
    # S.IndexBF(pos, T)

    S = StringList()
    S.CreateString()
    print("主串为：", end='')
    S.StringTraverse()
    print()
    T = StringList()
    T.CreateString()
    print("模式串为：", end='')
    T.StringTraverse()
    pos = int(input("\n请输入从主串的哪一位置开始串的模式匹配："))
    print("\n借助ListNext值的匹配结果：", end='')
    S.IndexKMP(pos, T, T.GetListNext())
    print("\n借助ListNextValue值的匹配结果：", end='')
    S.IndexKMP(pos, T, T.GetListNextValue())
    print(T.GetListNextValue())
